Elementary extension
If M'' ⊆ ''N is an inclusion of structures, we say that N'' is an '''elementary extension' of M'', or ''M is an elementary substructure of N'', denoted M \preceq N , if for every formula \phi(x) and every tuple b in ''M, we have : M \models \phi(b) \iff N \models \phi(b) . In other words, if b'' satisfies \phi(x) in one of ''M and N'', then it must satisfy it in the other. Specializing to the case where ''x is a tuple of length 0, we recover elementary equivalence: if N'' is an elementary extension of ''M then M'' ≡ ''N. However, M \preceq N is a strictly stronger condition than M \subseteq N plus M \equiv N . The elementary inclusion relation is transitive: if M \preceq M' \preceq M'' , then M \preceq M'' . Non-examples The rationals are not an elementary substructure of the reals (as rings): \mathbb{Q} \not\preceq \mathbb{R} . For example, if \phi(x) is the formula asserting that x'' is a square: : \phi(x) \iff \exists y : x = y^2 , then : \mathbb{Q} \not \models \phi(2) but \mathbb{R} \models \phi(2) because 2 is a square in the reals, but not the rationals. It is possible for ''M ⊆ N'' and ''M ≡ N'' to hold without ''N being an elementary extension of M''. For example, let ''N be the natural numbers {0,1,2,...} with the structure of an ordered set. Let M'' be the subset {1,2,3,...}. Then ''M is a substructure of N'' and ''M is elementarily equivalent to N'' (because ''M and N'' are isomorphic). However, M \not \preceq N . Indeed, if \phi(x) is the formula : \exists y : y < x , then \phi(1) holds in ''N, but not M'', because 1 is not the least element in ''N, but it is the least element in M''. Examples If ''M ⊆ N'', and ''b is a tuple from M'', and \phi(x) is a ''quantifier-free formula, then : M \models \phi(b) \iff N \models \phi(b) is automatic. Consequently, if T'' is a theory with quantifier elimination, then any inclusion of models is an elementary inclusion. Indeed, if ''M ⊆ N'', \psi(x) is an arbitrary formula, then we can find an equivalent quantifier-free formula \phi(x) . Then for a tuple ''b from M'', : M \models \psi(b) \iff M \models \phi(b) \iff N \models \phi(b) \iff N \models \psi(b) . More generally, if ''T is model complete, then any inclusion of models of T'' is an elementary inclusion. In fact, this is one way of characterizing model completeness. From this, one gets many examples of elementary extensions: * The algebraic numbers are an elementary substructure of the field of complex numbers (because ACF is model complete). * The real algebraic numbers are an elementary substructure of the field of real numbers (because RCF is model complete). * Any extension of non-trivially valued algebraically closed valued fields is an elementary extension, because ACVF is model complete. The Tarski-Vaught Criterion '''Theorem:' Let M'' be a structure, and ''S be a subset of M''. Then ''S is an elementary substructure of M'' if and only if the following property holds: for every formula \phi(x;y) and every tuple ''b ∈ S'', if \phi(M;b) is non-empty, then it intersects ''S. In other words, every non-empty subset of M'' definable over ''S intersects S''. (This is called the '''Tarski-Vaught Criterion'.) Proof: First suppose that S'' is an elementary substructure of ''M. Let \phi(x;y) be a formula. Suppose that \phi(M;b) is non-empty. Then : M \models \exists x : \phi(x;b) . In particular, b'' satisfies the formula \exists x : \phi(x;y) . Because S \preceq M , we conclude that : S \models \exists x : \phi(x;b) Therefore there is some ''a in S'' such that : S \models \phi(a,b) Again, because S \preceq M , we conclude : M \models \phi(a,b) . Therefore a \in \phi(M;b) , so \phi(M;b) intersects ''S. Conversely, suppose the Tarski-Vaught criterion holds. We prove by induction on n'' that if \psi(x) is a formula in prenex form with ''n quantifiers, then : \psi(S) = \psi(M) \cap S , which is exactly the condition necessary for S \preceq M to hold. Since every formula can be written in prenex form, this will suffice. The base case where n'' = 0 is the case where \psi(x) is quantifier-free. In this case, it is automatically true that \psi(S) = \psi(M) \cap S , without any assumptions on ''S or M''. For the inductive step, write \psi(x) as \exists y : \chi(x;y) or \forall y : \chi(x;y) for some formula \chi(x;y) with one fewer quantifier. The existential and universal case are related by negation, so it suffices to consider the existential case. The inductive hypothesis says that if ''a and b'' are tuples from ''S, then : S \models \chi(a;b) \iff M \models \chi(a;b) Let a'' be a tuple from ''S, we want to show that : S \models \exists y : \chi(a;y) \iff M \models \exists y : \chi(a;y) (*') Suppose the right hand side holds. Then there is ''b in S such that : S \models \chi(a;b) By the inductive hypothesis : M \models \chi(a;b) and therefore M \models \exists y : \chi(a;y) . So the right hand side of (*') implies the left hand side. Conversely, suppose that M \models \exists y : \chi(a;y) . Then \chi(a;M) is non-empty, so it intersects ''S; let b'' be some point of intersection. Thus : M \models \chi(a;b) and ''b is in S''. By the inductive hypothesis, : S \models \chi(a;b) and therefore S \models \exists y : \chi(a;y) . So the two sides of ('*') are equivalent. QED. Elementary Chains An elementary chain is a chain of models : M_1 \subset M_2 \subset \cdots such that M_i \preceq M_j for ''i ≤ j''. (The chain could have transfinite length). The 'Tarski-Vaught Theorem' on unions of elementary chains says that the union structure : \bigcup_i M_i is an elementary extension of ''Mj for each j''. Elementary Amalgamation Theorem An '''elementary embedding' is an injective map f'': ''M -> N'' which induces an isomorphism between ''M and an elementary substructure of N''. For example, any inclusion of an elementary substructure into an elementary extension is an elementary embedding. The '''Elementary Amalgamation Theorem' says that if f''1: ''M -> N''1 and ''f''2: ''M -> N''2 are two elementary embeddings, then there is a structure ''N''3 and elementary embeddings ''g''1 : ''N''1 -> ''N''3 and ''g''2 : ''N''2 -> ''N''3 such that everything commutes: : g_1 \circ f_1 = g_2 \circ f_2 In other words, if ''M can be elementarily embedded into two structures N''1 and ''N''2, then there is an elementary extension of ''M into which both N''1 and ''N''2 can be embedded over ''M. This theorem can be proven by extending tp(N''1/''M) to ''N''2 and realizing the resulting type in an elementary extension of ''N''2.